// 动态规划; 时间复杂度O(n); 空间复杂度O(1)

class Solution {
public:
    int numDecodings(string s) {
        auto onedigit = [](char ch) -> int {
            if (ch == '*') return 9;
            if (ch == '0') return 0;
            return 1;
        };
        auto twodigits = [](char ch0, char ch1) -> int {
            if (ch0 == '*' && ch1 == '*') return 15;
            if (ch0 == '*') {
                if (ch1 >= '0' && ch1 <= '6') return 2;
                else return 1;
            }
            if (ch1 == '*') {
                if (ch0 == '1') return 9;
                else if (ch0 == '2') return 6;
                else return 0;
            }
            if (ch0 == '1' || ch0 == '2' && ch1 >= '0' && ch1 <= '6') return 1;
            return 0;
        };
        int n = s.size();
        int pre0 = 0, pre1 = 1, cur = 0;
        for (int i = 0; i < n; i++) {
            cur = ((long long)pre1 * onedigit(s[i])) % 1000000007;
            if (i > 0) {
                cur = (cur + (long long)pre0 * twodigits(s[i - 1], s[i])) %  1000000007;
            }
            pre0 = pre1;
            pre1 = cur;
        }
        return cur;
    }
};